package com.sxu.greedy.day4;

/**
 * 加油站
 */
public class Test18 {
    // 暴力解法 —— 超时
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int n = gas.length;
        // 穷举所有起点
        for(int i = 0; i < n; i++) {
            int rest = 0; // 统计净收益
            // 向后走的步数
            for(int step = 0;step < n;step++) {
                int index = (i + step) % n; // 走step步后的下标
                rest = rest + gas[index] - cost[index];
                if(rest < 0) {
                    break;
                }
            }
            if(rest >= 0) {
                return i;
            }
        }
        return -1;
    }

    // 优化 - 贪心/找规律 —— O（N）
    public int canCompleteCircuit2(int[] gas, int[] cost) {
        int n = gas.length;
        // 穷举所有起点
        for(int i = 0; i < n; i++) {
            int rest = 0; // 统计净收益
            int step = 0;
            // 向后走的步数
            for(;step < n;step++) {
                int index = (i + step) % n; // 走step步后的下标
                rest = rest + gas[index] - cost[index];
                if(rest < 0) {
                    break;
                }
            }
            if(rest >= 0) {
                return i;
            }
            // i = i + step + 1;
            i = i + step; // 后续i会++，所以只需要加step即可
        }
        return -1;
    }
}
